package history

import "go-study/src/leetcode"

/**
 * @Description: 160. Intersection of Two Linked Lists 简单
 * @Keyword: 长链先动
 * @Author: kami
 * @Date: 2022/5/29 21:06
 **/
func getIntersectionNode(headA, headB *leetcode.ListNode) *leetcode.ListNode {
	var curA = headA
	var curB = headB
	var cntA = 1
	var cntB = 1
	for curA.Next != nil {
		cntA++
		curA = curA.Next
	}
	for curB.Next != nil {
		cntB++
		curB = curB.Next
	}
	// a链为长链
	if cntB > cntA {
		headA, headB = headB, headA
		cntA, cntB = cntB, cntA
	}
	var skipStep = cntA - cntB
	for i := 0; i < cntA; i++ {
		if i < skipStep {
			headA = headA.Next
			continue
		}
		if headA == headB {
			return headB
		}
		headA = headA.Next
		headB = headB.Next
	}
	return nil
}

/*
	双链加和等长法
*/
func getIntersectionNode1(headA, headB *leetcode.ListNode) *leetcode.ListNode {
	if headA == nil || headB == nil {
		return nil
	}

	var curA = headA
	var curB = headB

	for curA != curB {
		if curA == nil {
			curA = headB
		} else {
			curA = curB.Next
		}
		if curB == nil {
			curB = headA
		} else {
			curB = curB.Next
		}
	}
	return curA
}
